{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最短路径的作业"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.1-1  \n",
    "### 1\n",
    "初始：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & ∞ & ∞ & ∞ & ∞ & 0\\\\\n",
    "\\Pi & NULL & NULL & NULL & NULL & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "第1轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 2 & ∞ & 7 & ∞ & 0\\\\\n",
    "\\Pi & z & NULL & z & NULL & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "第2轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 2 & 5 & 7 & 9 & 0\\\\\n",
    "\\Pi & z & x & z & s & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "第3轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 2 & 5 & 6 & 9 & 0\\\\\n",
    "\\Pi & z & x & y & s & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "第4轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 2 & 4 & 6 & 9 & 0\\\\\n",
    "\\Pi & z & x & y & s & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "无负环，输出True\n",
    "### 2\n",
    "初始：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 0 & ∞ & ∞ & ∞ & ∞\\\\\n",
    "\\Pi & NULL & NULL & NULL & NULL & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "第1轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 0 & 6 & ∞ & 7 & ∞\\\\\n",
    "\\Pi & NULL & s & NULL & s & NULL\n",
    "\\end{array}\n",
    "$$\n",
    "第2轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 0 & 6 & 4 & 7 & 2\\\\\n",
    "\\Pi & NULL & s & y & s & t\n",
    "\\end{array}\n",
    "$$\n",
    "第3轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 0 & 2 & 4 & 7 & 2\\\\\n",
    "\\Pi & NULL & x & y & s & t\n",
    "\\end{array}\n",
    "$$\n",
    "第4轮遍历后：\n",
    "$$\n",
    "\\begin{array}{cccccc}\n",
    "V & s & t & x & y & z\\\\\n",
    "\\hline\n",
    "D & 0 & 2 & 4 & 7 & -2\\\\\n",
    "\\Pi & NULL & x & y & s & t\n",
    "\\end{array}\n",
    "$$\n",
    "有负环，输出False"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.1-3\n",
    "每次遍历全部边后检查dist数组是否发生了改变，若未改变，则算法直接停止。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.4-1\n",
    "对问题进行图建模，共6个顶点，10条边。代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "可行解:[-5.0, -3.0, 0.0, -1.0, -6.0, -8.0]\n"
     ]
    }
   ],
   "source": [
    "# 邻接表\n",
    "graph = {\n",
    "    0: {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0},\n",
    "    1: {5: -1},\n",
    "    2: {1: 1, 4: 2},\n",
    "    3: {2: 2, 6: -8},\n",
    "    4: {1: -4, 5: 3},\n",
    "    5: {2: 7},\n",
    "    6: {2: 5, 3: 10},\n",
    "}\n",
    "\n",
    "\n",
    "def SPFA(graph: dict, arc_num: int):\n",
    "    que = [0]  # 队列\n",
    "    book = [0 for _ in range(7)]  # 记录顶点入队了几次\n",
    "    # 距离数组，记录0到各顶点的最短距离\n",
    "    dis = [float(\"inf\") if i != 0 else 0. for i in range(7)]\n",
    "    while len(que) != 0:\n",
    "        u = que[0]  # 取出队首元素\n",
    "        del que[0]  # 出队\n",
    "        for v, wei in graph[u].items():\n",
    "            if dis[v] > wei+dis[u]:  # 松弛\n",
    "                dis[v] = wei+dis[u]\n",
    "                book[v] += 1\n",
    "                que.append(v)  # 松弛成功的顶点入队\n",
    "                if book[v] > arc_num-1:\n",
    "                    return dis, False  # 有负环\n",
    "    return dis, True\n",
    "\n",
    "\n",
    "dis, ans = SPFA(graph, 16)\n",
    "if ans:\n",
    "    print(\"可行解:{}\".format(dis[1:]))\n",
    "else:\n",
    "    print(\"无解。\")\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24-3\n",
    "### a\n",
    "首先，我们取汇率$R[i_1,i_2]$的负对数$-ln(R[i_1,i_2])$作为权值进行图建模。   \n",
    "即对于每一对顶点$i_1,i_2$，它们的边权设置成$-ln(R[i_1,i_2])$。    \n",
    "之后，判断是否有套利交易序列即转化成判断图中是否有负权环。使用$Bellman-Ford$或$SPFA$算法即可解决这个问题。\n",
    "### b\n",
    "使用$SPFA$算法，时间复杂度为$O(kE)$($E$是边数)   \n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def SPFA(graph: dict, arc_num: int) -> bool:\n",
    "    que = [0]  # 队列\n",
    "    book = [0 for _ in range(7)]  # 记录顶点入队了几次\n",
    "    # 距离数组，记录0到各顶点的最短距离\n",
    "    dis = [float(\"inf\") if i != 0 else 0. for i in range(7)]\n",
    "    while len(que) != 0:\n",
    "        u = que[0]  # 取出队首元素\n",
    "        del que[0]  # 出队\n",
    "        for v, wei in graph[u].items():\n",
    "            if dis[v] > wei+dis[u]:  # 松弛\n",
    "                dis[v] = wei+dis[u]\n",
    "                book[v] += 1\n",
    "                que.append(v)  # 松弛成功的顶点入队\n",
    "                if book[v] > arc_num-1:\n",
    "                    return False  # 有负环\n",
    "    return True"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 25.2-1\n",
    "初始：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & ∞ & ∞ & ∞ & -1 & ∞\\\\\n",
    "1 & 0 & ∞ & 2 & ∞ & ∞\\\\\n",
    "∞ & 2 & 0 & ∞ & ∞ & -8\\\\\n",
    "-4 & ∞ & ∞ & 0 & 3 & ∞\\\\\n",
    "∞ & 7 & ∞ & ∞ & 0 & ∞\\\\\n",
    "∞ & 5 & 10 & ∞ & ∞ & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "第1轮遍历：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & ∞ & ∞ & ∞ & -1 & ∞\\\\\n",
    "1 & 0 & ∞ & 2 & 0 & ∞\\\\\n",
    "∞ & 2 & 0 & ∞ & ∞ & -8\\\\\n",
    "-4 & ∞ & ∞ & 0 & -5 & ∞\\\\\n",
    "∞ & 7 & ∞ & ∞ & 0 & ∞\\\\\n",
    "∞ & 5 & 10 & ∞ & ∞ & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "第2轮遍历：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & ∞ & ∞ & ∞ & -1 & ∞\\\\\n",
    "1 & 0 & ∞ & 2 & 0 & ∞\\\\\n",
    "3 & 2 & 0 & 4 & 2 & -8\\\\\n",
    "-4 & ∞ & ∞ & 0 & -5 & ∞\\\\\n",
    "8 & 7 & ∞ & 9 & 0 & ∞\\\\\n",
    "6 & 5 & 10 & 7 & 5 & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "第3轮遍历：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & ∞ & ∞ & ∞ & -1 & ∞\\\\\n",
    "1 & 0 & ∞ & 2 & 0 & ∞\\\\\n",
    "3 & 2 & 0 & 4 & 2 & -8\\\\\n",
    "-4 & ∞ & ∞ & 0 & -5 & ∞\\\\\n",
    "8 & 7 & ∞ & 9 & 0 & ∞\\\\\n",
    "6 & 5 & 10 & 7 & 5 & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "第4轮遍历：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0 & ∞ & ∞ & ∞ & -1 & ∞\\\\\n",
    "-2 & 0 & ∞ & 2 & -3 & ∞\\\\\n",
    "0 & 2 & 0 & 4 & -1 & -8\\\\\n",
    "-4 & ∞ & ∞ & 0 & -5 & ∞\\\\\n",
    "5 & 7 & ∞ & 9 & 0 & ∞\\\\\n",
    "3 & 5 & 10 & 7 & 2 & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "第5轮遍历：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    " 0 & 6 & \\infty & 8 & -1 & \\infty \\\\\n",
    "-2 & 0 & \\infty & 2 & -3 & \\infty \\\\\n",
    " 0 & 2 &      0 & 4 & -1 &     -8 \\\\\n",
    "-4 & 2 & \\infty & 0 & -5 & \\infty \\\\\n",
    " 5 & 7 & \\infty & 9 &  0 & \\infty \\\\\n",
    " 3 & 5 &     10 & 7 &  2 & 0\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "第6轮遍历：\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    " 0 &  6 & \\infty &  8 & -1 & \\infty \\\\\n",
    "-2 &  0 & \\infty &  2 & -3 & \\infty \\\\\n",
    "-5 & -3 &      0 & -1 & -6 &     -8 \\\\\n",
    "-4 &  2 & \\infty &  0 & -5 & \\infty \\\\\n",
    " 5 &  7 & \\infty &  9 &  0 & \\infty \\\\\n",
    " 3 &  5 &     10 &  7 &  2 & 0\n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 25.2-6\n",
    "若输出的dist矩阵中的主对角线上有负值，说明存在负环。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 25.2-7\n",
    "$\\phi_{ij}^k$的递推式：\n",
    "$$\n",
    "\\phi_{ij}^k = \n",
    "\\left\\{\n",
    "\\begin{aligned}\n",
    "& \\phi_{ij}^{k-1}\\qquad(d_{ik}^{k} + d_{kj}^{k} \\ge d_{ij}^{k - 1})\\\\\n",
    "& k\\qquad(d_{ik}^{k} + d_{kj}^{k} < d_{ij}^{k - 1})\n",
    "\\end{aligned}\n",
    "\\right.\n",
    "$$\n",
    "修改后的$Floyd$算法如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Floyd(graph: list):\n",
    "    dist = graph\n",
    "    vex_num = len(graph)\n",
    "    phi = [[float(\"inf\") if i != j else 0 for i in range(vex_num)]\n",
    "           for j in range(vex_num)]\n",
    "    for k in range(vex_num):\n",
    "        for i in range(vex_num):\n",
    "            for j in range(vex_num):\n",
    "                if dist[i][k]+dist[k][j] < dist[i][j]:\n",
    "                    phi[i][j] = k\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
